
//https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&tqId=23255&ru=%2Fpractice%2F8c82a5b80378478f9484d87d1c5f12a4&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//动态规划：f(n)=f(n-1)+f(n-2);
//递归实现：时间复杂度是2的n次方，效率很低；

#include <iostream>

using namespace std;

class Solution1 {
public:
    int Fibonacci(int n) {
        // write code here
        if (n<=2) return 1;
        int n_1 = 1,n_2 = 1;
        int cur_num = 0;
        for(int i =3;i <=n;++i) {
            cur_num = n_1+n_2;
            n_2 =n_1;
            n_1 = cur_num;
        }
        return cur_num;
    }
};

class Solution2 {
public:
    int Fibonacci(int n) {
        // write code here
        if (n <= 0) return 0;
        if (n <= 2) return 1;
        return Fibonacci(n-1) + Fibonacci(n-2);
}
};